package dp;

import org.junit.Test;

public class EditDistance72 {

    @Test
    public void test() {
//        minDistanceBasedOnLCS("intention", "execution");
//        minDistanceBasedOnLCS("intentiona", "executionb");
//        minDistanceBasedOnLCS("aintention", "bexecution");
//        minDistanceBasedOnLCS("aintention", "aexecution");

        // wrong steps 5, expect 3
//        minDistanceBasedOnLCS("mart", "karma");
//
//        minDistance("intention", "execution");
//        minDistance("intentiona", "executionb");
//        minDistance("aintention", "bexecution");
//        minDistance("aintention", "aexecution");
        minDistance("mart", "karma");
    }

    public int minDistance(String w1, String w2) {
        System.out.println("---------------------------");
        // dp[i+1][j+1] 表示 w1[0:i] 与 w2[0:j] 的编辑距离
        int[][] dp = new int[w1.length()+1][w2.length()+1];

        // act[i+1][j+1] 表示 这一步要做的编辑操作
        int[][] act = new int[w1.length()+1][w2.length()+1];

        // w1[i] = w2[j], do nothing
        final int NOOP = 0;

        // 原 dp[i+1][j] 已经完成了从 w1[0:i] 变到 w2[0:j-1], 现在 act[i+1][j+1] 只能在 w2[0:j-1] 末尾插入 w2[j] 来变为 w2[0:j].
        final int INSERT = 1;

        // 原 dp[i][j+1] 已经完成了从 w1[0:i-1] 变到 w2[0:j], 现在 act[i+1][j+1] 只能在 w1[0:i-1] 末尾删除 w1[i] 来保持 w2[0:j] 不变.
        final int DELETE = 2;

        // 原 dp[i][j] 已经完成了从 w1[0:i-1] 变到 w2[0:j-1], 且 w1[i] != w2[j], 现在 act[i+1][j+1] 只能将 w1[i] 替换为 w2[j] 来变为 w2[0:j].
        final int REPLACE = 3;

        dp[0][0] = 0;
        act[0][0] = NOOP;

        // 初始化: w1 变为 空串, 全删除, 注意i要从1开始, 不能修改dp[0][0]
        for (int i = 1; i <= w1.length(); i++) {
            dp[i][0] = i;
            act[i][0] = DELETE;
        }

        // 初始化: 从 空串 变 w2, 全插入, 注意j要从1开始, 不能修改dp[0][0]
        for (int j = 1; j <= w2.length(); j++) {
            dp[0][j] = j;
            act[0][j] = INSERT;
        }

        for (int i = 0; i < w1.length(); i++) {
            for (int j = 0; j < w2.length(); j++) {
                if (w1.charAt(i) == w2.charAt(j)) {
                    dp[i+1][j+1] = dp[i][j];
                    act[i+1][j+1] = NOOP;
                } else {
                    int min = Integer.MAX_VALUE;
                    int action = NOOP;

                    // 不能用if-else, shit
                    if (dp[i+1][j] < min) {
                        min = dp[i+1][j];
                        action = INSERT;
                    }
                    if (dp[i][j+1] < min) {
                        min = dp[i][j+1];
                        action = DELETE;
                    }
                    if (dp[i][j] < min) {
                        min = dp[i][j];
                        action = REPLACE;
                    }

                    dp[i+1][j+1] = min + 1;
                    act[i+1][j+1] = action;
                }
            }
        }
        System.out.format("%s, %s, steps: %d\n", w1, w2, dp[w1.length()][w2.length()]);
        printMatrix(dp);
        printMatrix(act);

        return dp[w1.length()][w2.length()];
    }

    /* 这种基于LCS DP表及Direction表的方式不是最优的, 虽然能找个一个编辑路径, 但编辑距离不是最优的 */
    public int minDistanceBasedOnLCS(String w1, String w2) {
        System.out.println("---------------------------");
        final int E = 3; // dp[i+1][j+1] <- dp[i][j] + 1
        final int X = 1; // dp[i+1][j+1] <- dp[i+1][j]
        final int Y = 2; // dp[i+1][j+1] <- dp[i][j+1]
        final int N = -1; // otherwise

        int[][] dp = new int[w1.length()+1][w2.length()+1];
        int[][] dirs = new int[w1.length()+1][w2.length()+1];
        for (int i = 0; i <= w1.length(); i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= w2.length(); j++) {
            dp[0][j] = 0;
        }

        for (int i = 0; i < w1.length(); i++) {
            for (int j = 0; j < w2.length(); j++) {
                int dir = N;
                int max = -1;
                if (w1.charAt(i) == w2.charAt(j)) {
                    max = dp[i][j] + 1;
                    dir = E;
                }
                if (dp[i][j+1] > max) {
                    max = dp[i][j+1];
                    dir = Y;
                }
                if (dp[i+1][j] > max) {
                    max = dp[i+1][j];
                    dir = X;
                }
                dp[i+1][j+1] = max;
                dirs[i+1][j+1] = dir;
            }
        }

        int i = w1.length();
        int j = w2.length();
        // assume there is a '$' after the tail of each word
        int lastEqualAtX = i + 1;
        int lastEqualAtY = j + 1;
        int steps = 0;
        while (i > 0 && j > 0) {
            if (dirs[i][j] == E) {
                System.out.format("i: %d, j: %d, lastEqualAtX: %d, lastEqualAtY: %d, steps: %d\n", i, j, lastEqualAtX, lastEqualAtY, steps);
                steps += Math.max(lastEqualAtX - i - 1, lastEqualAtY - j - 1);
                lastEqualAtX = i;
                lastEqualAtY = j;
                i--;
                j--;
            } else if (dirs[i][j] == X) {
                j--;
            } else if (dirs[i][j] == Y) {
                i--;
            }
        }

        steps += Math.max(lastEqualAtX - 1, lastEqualAtY - 1);
        System.out.format("i: %d, j: %d, lastEqualAtX: %d, lastEqualAtY: %d, steps: %d\n", i, j, lastEqualAtX, lastEqualAtY, steps);

        System.out.format("%s, %s, LCS: %d, steps: %d\n", w1, w2, dp[w1.length()][w2.length()], steps);
        printMatrix(dp);
        printMatrix(dirs);
        return steps;
    }

    public static void printMatrix(int[][] m) {
        printMatrix(m, m.length, m[0].length);
    }

    public static void printMatrix(int[][] m, int x, int y) {
        for (int j = 0; j < y; j++) {
            System.out.format("\t%d", j);
        }
        System.out.println();
        for (int i = 0; i < x; i++) {
            System.out.format("%d:", i);
            for (int j = 0; j < y; j++) {
                System.out.format("\t%d", m[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }
}
